1. Field of the Invention
The present invention relates to systems and methods of encoding and decoding digital data which is being transmitted in order to reduce the likelihood of errors in the received digital data caused, for example, by noise associated with the transmission of the data.
2. Description of the Prior Art
The transmission of data between two locations presents the danger that the data will be corrupted by noise or by malfunction of either the transmitter or the receiver. In order to reduce the likelihood of errors corrupting transmitted data, it is well-known to encode the data prior to transmission, and to decode the received signals to convert those received signals back to the digital data. The encoding and decoding of the data typically involves adding check bits which allow the decoder to detect the presence of errors in the received signals. In some cases, the particular code used for encoding the data permits the decoder not only to detect the presence of some transmission errors, but also to correct certain of those errors.
One such error detecting and correcting code is the (8, 4) single-error correcting, double-error detecting Hamming code. The Hamming code involves the generation of an eight-bit code vector from four information or message bits by adding four check bits. The code vectors have a minimum Hamming distance of 4. This means that all code vectors have a weight of either 0, 4 or 8. As used in this context, "weight" is defined as the total number of "1's" present in the code vector. In the Hamming code, there is one eight-bit code vector possible with a weight of 0, one code vector possible with a weight of 8, and all other possible code vectors have a weight of 4. All of the Hamming code vectors satisfy the matrix product gH.sup.t =0, where g is a code vector, where H is the check matrix of the Hamming (8, 4) code, and where addition is modulo 2. The check matrix of the (8, 4) Hamming code is ##EQU1##
Although the (8, 4) Hamming code allows the decoder to correct all single errors and to detect all double errors in the received code vector, the decoder cannot detect errors of multiplicity greater than 2. As a result, long bursts of errors caused by noise or by malfunctions of either the transmitter or the receiver may not be detected using the (8, 4) Hamming code.
There is a continuing need for improved codes to be used in encoding and decoding transmitted data which have a relatively high ratio of information bits to check bits, and yet provide improved error correction and error detection capabilities.